There has been an increasing demand to provide ubiquitous mobile access for a multitude of services ranging from conventional data to real-time streaming applications. To meet such requirements, existing cellular systems need to be enhanced to provide improved data rates and connectivity.
Adding less sophisticated and less expensive “relay” stations (RS) to a network helps improve the throughput and coverage in the network. The introduction of relay stations transforms the network into a two-hop network, which is not as complex as a multi-hop network but at the same time not as straight-forward as a cellular network, thereby allowing for unique optimizations. Such two-hop networks not only provide multi-user and channel diversity gains available in conventional one-hop orthogonal frequency-division multiple access (OFDMA) cellular systems, but also provide cooperative diversity gains due to the presence of relays. Furthermore, in addition to diversity within hops, two-hop networks also provide diversity gains across hops.
Scheduling is an important component in the efficient exploitation of the diversity gains delivered by two-hop relay-assisted cellular networks. Known approaches leverage only the multi-user and channel diversity gains available in one-hop cellular networks. (See Z. Zhang et al., “Opportunistic downlink scheduling for multiuser OFDM systems,” IEEE WCNC, March 2005; and G. Song et al., “Cross-layer optimization for OFDM wireless networks—Part I: Theoretical Framework,” IEEE Transactions on Wireless Communications, vol. 4, no. 2, March 2005.) Approaches that consider relay cooperation focus on the design of cooperation strategies but do not provide efficient scheduling algorithms that are capable of leveraging these cooperative gains, when made available. (See A. So et al., “Effect of relaying on capacity improvement in wireless local area networks,” in IEEE WCNC, March 2005; and P. Herhold et al., “Relaying in cdma networks: pathloss reduction and transmit power savings,” in IEEE VTC, April 2003.) On the other hand, approaches that consider scheduling in relay networks do not leverage diversity across hops. (See S. Mengesha et al., “Relay routing and scheduling for capacity improvement in cellular wlans,” in WiOpt: Modeling and Optimization in Mobile, Ad-hoc and Wireless Networks,” March 2003; and N. Challa et al., “Cost-aware downlink scheduling of shared channels for cellular networks with relays,” IEEE International Conference on Performance Computing and Communications, 2004.)
Furthermore, known scheduling solutions do not incorporate finite data in user buffers and instead assume backlogged data. In fact, data in user buffers is limited in practice and incorporation of this aspect changes the problem considerably, making it more difficult. The problem of determining the optimal diversity schedule across two hops in the presence of finite user buffers is an NP-hard problem, which is even hard to approximate and hence no optimal solution exists that runs in polynomial time.
The efficient exploitation of the diversity gains at the base station (BS) of a two-hop relay-assisted cellular network requires more sophisticated solutions than those currently available.